/**
 * 983. 最低票价
 * https://leetcode-cn.com/problems/minimum-cost-for-tickets/
 */
public class Solutions_983 {
    public static void main(String[] args) {
//        int[] days = {1, 4, 6, 7, 8, 20}, costs = {2, 7, 15};  // output: 11
        int[] days = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}, costs = {2, 7, 15};  // output: 17

        int result = mincostTickets(days, costs);
        System.out.println(result);
    }

    /**
     * 解题思路：动态规划（从后往前推导）
     */
    public static int mincostTickets(int[] days, int[] costs) {
        int len = days.length;
        // 开始旅行的天数与结束旅行的天数
        int minDay = days[0], maxDay = days[len - 1];
        // dp[1] = 17：表示第 1 天时，最少花费 17 美元，可完成旅行 days 中的全部天数
        int[] dp = new int[maxDay + 1 + 30];
        int idx = len - 1;
        // 依次遍历 [minDay, maxDay]
        for (int i = maxDay; i >= minDay; i--) {
            if (i == days[idx]) {
                // 若第 8 天有安排旅行，则有三种选择：1 天的通行证，7 天的通行证，30 天的通行证
                // 通行证费用与 1、7、30 天后的消费分别相加并取最小值
                int cost = Math.min(dp[i + 1] + costs[0], dp[i + 7] + costs[1]);
                cost = Math.min(cost, dp[i + 30] + costs[2]);
                dp[i] = cost;
                idx --;
            } else {
                // 若第 8 天没有旅行，则第 8 天的花费就等于第 9 天的花费
                dp[i] = dp[i + 1];
            }
        }
        return dp[minDay];
    }
}
